Under present communication environments, various communication networks such as a broadband convergence network (BcN) enabling services such as cooperation of wired and wireless communications and convergence of broadcast networks and communication networks are combined and this trend will be accelerated.
General-purpose media communications have been much studied with the trend of digital convergence in various communication networks, and size transformation techniques for video have been variously studied with an increase in diversity of multimedia terminals.
Among the size transformation techniques of video, a method employing discrete cosine transform (DCT) exhibits excellent performance. The DCT is also used in video codecs such as MPEG-1, MPEG-2, MPEG-4, and H.263, which have excellent compatibility.
The DCT is a transformation technique of an input analog original video into frequency components of a low frequency and a high frequency through the use of the mathematically defined process of DCT.
The DCT/IDCT techniques according to the background art will be described below in brief
The mathematical definition of N×N 2D-DCT/IDCT according to the background art will be first described. Expression 1 represents the mathematical definition of IDCT and Expression 2 represents the mathematical definition of DCT.
                              f          ⁡                      (                          x              ,              y                        )                          =                              2            N                    ⁢                                    ∑                              u                =                0                                            N                -                1                                      ⁢                                                  ⁢                                          ∑                                  v                  =                  0                                                  N                  -                  1                                            ⁢                                                          ⁢                                                C                  ⁡                                      (                    u                    )                                                  ⁢                                  C                  ⁡                                      (                    v                    )                                                  ⁢                                  F                  ⁡                                      (                                          u                      ,                      v                                        )                                                  ⁢                cos                ⁢                                                                            (                                                                        2                          ⁢                                                                                                          ⁢                          x                                                +                        1                                            )                                        ⁢                    u                    ⁢                                                                                  ⁢                    π                                                        2                    ⁢                                                                                  ⁢                    N                                                  ⁢                cos                ⁢                                                                            (                                                                        2                          ⁢                                                                                                          ⁢                          y                                                +                        1                                            )                                        ⁢                    v                    ⁢                                                                                  ⁢                    π                                                        2                    ⁢                                                                                  ⁢                    N                                                                                                          Expression        ⁢                                  ⁢        1                                                      F            ⁡                          (                              u                ,                v                            )                                =                                    2              N                        ⁢                          C              ⁡                              (                u                )                                      ⁢                          C              ⁡                              (                v                )                                      ⁢                                          ∑                                  x                  =                  0                                                  N                  -                  1                                            ⁢                                                          ⁢                                                ∑                                      y                    =                    0                                                        N                    -                    1                                                  ⁢                                                                  ⁢                                                      f                    ⁡                                          (                                              x                        ,                        y                                            )                                                        ⁢                  cos                  ⁢                                                                                    (                                                                              2                            ⁢                                                                                                                  ⁢                            x                                                    +                          1                                                )                                            ⁢                      u                      ⁢                                                                                          ⁢                      π                                                              2                      ⁢                                                                                          ⁢                      N                                                        ⁢                  cos                  ⁢                                                                                    (                                                                              2                            ⁢                                                                                                                  ⁢                            y                                                    +                          1                                                )                                            ⁢                      v                      ⁢                                                                                          ⁢                      π                                                              2                      ⁢                                                                                          ⁢                      N                                                                                                          ⁢                                  ⁢                              C            ⁡                          (              u              )                                ,                                    C              ⁡                              (                v                )                                      =                          {                                                                                                                  1                                                  2                                                                    ,                                                                                                                          for                        ⁢                                                                                                  ⁢                        u                                            ,                                              v                        =                        0                                                                                                                                                        1                      ,                                                                            otherwise                                                                                                          Expression        ⁢                                  ⁢        2            
In the expressions, x and y represent an x coordinate and an y coordinate in a pixel domain and f(x, y) represent a pixel value corresponding to a coordinate (x, y), in the expressions, u and v represent a u coordinate and a v coordinate in a frequency domain and F(u, v) represent a coefficient value corresponding to a coordinate (u, v) in a DCT domain. N represents the size. For example, when N is 8, the IDCT/DCI' is performed on total 64 pixels of 8×8. C(u) and C(v) represent scaling factors, respectively.
When N=8 (that is, 8×8 block) is assumed which is the value most used in image or video compression standards for performing the IDCT using Expression 1, the necessary operation includes 4096 multiplications and 4032 additions.
However, since this is an excessive operation load for use in an actual system, the IDCT/DCT using row-column decomposition is more used than the approach based on the mathematical definitions of Expressions 1 and 2 in practice. According to the row-column decomposition, the primary DCT/IDCT is performed by the number of columns in the row direction and the primary IDCT/DCT is performed by the number of rows in the column direction. Therefore, in the case of 8×8 block, the primary DCT/IDCT is performed 8 times in the row direction and the primary DCT/IDCT is performed 8 times in the column direction, that is, the primary DCT/IDCT is performed 16 times in total.
FIG. 1 is a diagram illustrating Chen's algorithm generally used in the row-column decomposition.
In order to perform a 2D-DCT/IDCT in the Chen's algorithm, the primary DCT/IDCT is performed by the number of columns in the row direction and then the primary DCT/IDCT is performed in the number of rows in the column direction. The values obtained through the primary DCT/IDCT in the row and column directions are the resultant values of the two-dimensional DCT/IDCT.
In the Chen's algorithm, the 2D-DCT/IDCT operation necessary for N=8 (that is, 8×8 block) includes 256 multiplications and 416 additions, which is much smaller than that in the approach based on the above-mentioned mathematical definitions.
However, the operation load is smaller than that of the existing DCT/IDCT, and there is still a problem in that input values on which it is not necessary to perform the DCT/IDCT are still included in the operation.
As described above, the DCT/IDCT techniques according to the background art have a problem in that a large operation load is required for the transformation process. Accordingly, phenomena of time delay and heat emission are caused in the transformation device and large energy consumption is also caused.
The row-column decomposition of which the operation load is considered to be much reduced has a problem in that an input value “0 (zero)” of which the operation is not necessary for using a butterfly structure is included in the DCT/IDCT operation. Accordingly, there is a problem in that the operation complexity unnecessarily increases.
The above-mentioned related art is technical information possessed to make the invention or learned in the course of making the invention by the inventor, and cannot thus be said to be technical information known to the public before filing the invention.